//! a prime-searching library for finding primes in given size
//!
//! Adapt from Plumb 's C library.
//! The algorithm refers and observes from ANSI X9.80
//! A simple bit sieve used for finding prime number candidates. Allows setting
//! and clearing of bits in a storage array. The size of the sieve is assumed to
//! be constant to reduce overhead. All the bits of a new bitSieve are zero, and
//! bits are removed from it by setting them.
//! To reduce storage space and increase efficiency, no even numbers are
//! represented in the sieve (each bit in the sieve represents an odd number).
//! The relationship between the index of a bit and the number it represents is
//! given by
//! N = offset + (2*index + 1);
//! Where N is the integer represented by a bit in the sieve, offset is some
//! even integer offset indicating where the sieve begins, and index is the
//! index of a bit in the sieve array.
//!
#[path = "mods/utils.rs"]
#[macro_use]
mod comparator;

use crate::mods::calculator::modulo_block;
use std::ops::{Index, Range};

/// Struct for Sieve Search
/// searches prime in Sieve's table every loop after eliminating primes' multiples
/// # Creating a Sieve
/// ```rust
/// use integer::prelude::*;
///
/// let small_sieve = Sieve::small_sieve(); // default size
///
/// /* search with offset and search limit, and the small_sieve helps search */
/// let searcher = Sieve::sieve(&[0, 1, 2], 1000, &small_sieve);
/// ```
pub struct Sieve {
    length: usize,
    size: usize,
    table: Vec<u64>,
}

impl Sieve {
    /// bit length is larger than this number will cause overflow
    pub const MAX_BIT_LEN: usize = 671088639;

    /// Making a searcher with a base offset and a limited search length
    ///
    /// *base* is a little-endian slice, *searchlen* represent the range of odd-number for
    /// searching, *small_sieve* helps to get the likely prime candidates.
    ///
    /// **Be aware of that** the output of searching with offset is just candidates without testing.
    pub fn sieve(base: &[u64], searchlen: usize, small_sieve: &Sieve) -> Self {
        let vec_size: usize = ((searchlen - 1) >> 6) + 1;
        let mut sieve = Sieve {
            length: searchlen,
            size: vec_size,
            table: vec![0u64; vec_size],
        };

        let (mut start, mut step) = (0usize, small_sieve.sieve_search(small_sieve.length, 0usize));
        let mut converted_step;

        while step < small_sieve.length {
            converted_step = (step * 2) + 1;
            // Calculate base mod convertedStep
            start = modulo_block(base, converted_step as u64) as usize;

            // Take each multiple of step out of sieve
            start = converted_step - start;
            if start % 2 == 0 {
                start += converted_step;
            }
            sieve.sieve_single(searchlen, (start - 1) / 2, converted_step);

            // Find next prime from small sieve
            step = small_sieve.sieve_search(small_sieve.length, step + 1);
        }
        sieve
    }

    /// flags off invertible numbers step by step
    pub fn sieve_single(&mut self, limit: usize, start: usize, step: usize) {
        for b in (start..limit).step_by(step) {
            self.set_bit(b);
        }
    }

    /// search the next number which is not labeled after start
    pub fn sieve_search(&self, limit: usize, start: usize) -> usize {
        let mut idx = start;
        while idx < limit && self.get_bit(idx) {
            idx += 1;
        }
        match idx >= limit {
            true => usize::MAX,
            false => idx,
        }
    }

    /// compute a proper size of sieve depending on bitlen
    #[inline]
    pub const fn invert_length(len: usize) -> usize {
        min!(len, Sieve::MAX_BIT_LEN) / 20 * 64
    }

    /// a small sieve with fixed (150 * 64) size
    pub fn small_sieve() -> Self {
        Self::small_sieve_with_size(150 * 64)
    }

    /// a small sieve with given size
    pub fn small_sieve_with_size(len: usize) -> Self {
        let vec_size: usize = ((len - 1) >> 6) + 1;
        let mut sieve = Sieve {
            length: len,
            size: vec_size,
            table: vec![0u64; vec_size],
        };

        // Mark 1 as composite
        sieve.set_bit(0);
        let (mut next_index, mut next_prime) = (1, 3);

        // Find primes and remove their multiples from sieve
        while next_index < len && next_prime < len {
            sieve.sieve_single(len, next_index + next_prime, next_prime);
            next_index = sieve.sieve_search(len, next_index + 1);
            next_prime = 2 * next_index + 1;
        }
        sieve
    }

    /// get sieve's size
    #[inline]
    pub const fn size(&self) -> usize {
        self.size
    }

    #[inline]
    fn set_bit(&mut self, b: usize) {
        self.table[b >> 6] |= 1u64 << (b & 0x3f);
    }

    #[inline]
    fn get_bit(&self, b: usize) -> bool {
        self.table[b >> 6] & (1u64 << (b & 0x3f)) != 0
    }
}

impl Index<usize> for Sieve {
    type Output = u64;

    fn index(&self, index: usize) -> &Self::Output {
        &self.table[index]
    }
}

impl Index<Range<usize>> for Sieve {
    type Output = [u64];

    fn index(&self, index: Range<usize>) -> &Self::Output {
        &self.table[index]
    }
}
